In the prior art, White et al, U.S. Pat. No. 4,199,661, "Method and Apparatus for Eliminating Conflicts on a Communication Channel", issued Apr. 22, 1980, shows that it is broadly known to alter a fixed priority protocol among a plurality of processors accessing a common channel to create another type of bias. As applied to crossbar switches, taken either singly or in multistage networks, these fixed priority protocols have been used in the implementation of processor-to-processor interconnections in highly parallel computers.
For purposes of this invention, a parallel computer is taken to mean any set of communicating processors.
For the purpose of this invention, a d-X-d crossbar switch comprises two sets of ports I(i) (inputs) and O(j) (outputs) and a set of switches s(ij), where i and j range from 1 to d. Each of the switches s(ij) can be open or closed. The effect of closing switch s(ij) is to establish a connection between port I(i) and port O(j). The connection can be unidirectional (data is only sent from inputs I(i) and outputs O(j)) or bidirectional (data can be sent back and forth between I(i) and O(j)). Also, for each i, at most one switch s(ij) is closed at any time; i.e. each I(i) is connected to at most one O(j). However, if multiple inputs i desire to transmit to a single output j, conflicts arise.
Prior art implementation has been designed upon several common assumptions. The first assumption is that the origin and destinations of messages are uniformly distributed. A second assumption is that the origin and destinations of different messages are independent. A third assumption is that conflicts among inputs of a crossbar for access to an output of the crossbar are resolvable by uniform and independent random selection of one of the competing inputs. By "random selection", it is meant either one based on the outcome of a truly random physical experiment, or one based on the outcome of a pseudo-random mathematical process.
It is believed that uniformity of traffic can be achieved by an appropriate design of communication protocols executable by the processors. Independence of traffic can be ensured by transmitting each message in two phases through a uniformly and independently selected intermediate processor. Thus, departures from independence of traffic should cause no more than a factor of two degradation.
Random conflict resolution can be ensured by design of the crossbars. However, this may be costly for two reasons. First, either random numbers must be generated in the processors, transmitted with the messages and captured by the crossbars, or they must be generated by the crossbars themselves. Second, the uniform selection of a competing input is a logically complicated function requiring many gates for its realization.
Illustratively, conflict resolution occurs between inputs i.sub.1, . . . , i.sub.s First, where a local random experiment is performed, it is necessary to determine the number of conflicting requests s. Next, it is necessary to pick a random number r between 1, . . . ,s and connect the input i.sub.r to the output. Alternatively, the processors send random numbers r.sub.1, . . . r.sub.s together with a request to connect i.sub.1, . . . , i.sub.s to a predetermined output. In this regard, it is necessary to receive r.sub.1, . . . , r.sub.s, determine the largest, say r.sub.max (not guaranteed to resolve conflict). Lastly, it is necessary to connect the input i.sub.max . It is also to be noted that the above mechanism has to be replicated for each output.